{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Deletions to Make Character Frequencies Unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDeletions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符频次唯一的最小删除次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果字符串 <code>s</code> 中 <strong>不存在</strong> 两个不同字符 <strong>频次</strong> 相同的情况，就称 <code>s</code> 是 <strong>优质字符串</strong> 。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code>，返回使 <code>s</code> 成为 <strong>优质字符串</strong> 需要删除的 <strong>最小</strong> 字符数。</p>\n",
    "\n",
    "<p>字符串中字符的 <strong>频次</strong> 是该字符在字符串中的出现次数。例如，在字符串 <code>\"aab\"</code> 中，<code>'a'</code> 的频次是 <code>2</code>，而 <code>'b'</code> 的频次是 <code>1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aab\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong><code>s</code> 已经是优质字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaabbbcc\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以删除两个 'b' , 得到优质字符串 \"aaabcc\" 。\n",
    "另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 \"aaabbc\" 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ceabaacb\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>可以删除两个 'c' 得到优质字符串 \"eabaab\" 。\n",
    "注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 仅含小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-deletions-to-make-character-frequencies-unique](https://leetcode.cn/problems/minimum-deletions-to-make-character-frequencies-unique/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-deletions-to-make-character-frequencies-unique](https://leetcode.cn/problems/minimum-deletions-to-make-character-frequencies-unique/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aab\"', '\"aaabbbcc\"', '\"ceabaacb\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        ls.sort()\n",
    "        print(ls)\n",
    "        res = 0\n",
    "        for i in range(24, -1, -1):\n",
    "            if ls[i] and ls[i]>=ls[i+1]:\n",
    "                res += ls[i]-ls[i+1]+(1 if ls[i+1]>0 else 0)\n",
    "                ls[i] = ls[i+1]-1 if ls[i+1]>0 else 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        sor = sorted(c.values(), reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(1, len(sor)):\n",
    "            if sor[i] >= sor[i - 1]:\n",
    "                target = max(0, sor[i - 1] - 1)\n",
    "                ans += sor[i] - target\n",
    "                sor[i] = target\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        cc = Counter(cnt.values())\n",
    "        mx = max(cc.keys())\n",
    "        ans = 0\n",
    "        while mx:\n",
    "            if cc[mx] > 1:\n",
    "                ans += cc[mx] - 1\n",
    "                cc[mx-1] += cc[mx] - 1\n",
    "            mx -= 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        freq = defaultdict(int)\n",
    "        for k, v in cnt.items():\n",
    "            freq[v] += 1\n",
    "        ret = 0\n",
    "        j = 10 ** 5\n",
    "        for f in sorted(freq.keys(), reverse=True):\n",
    "            num = freq[f] - 1\n",
    "            if num == 0:\n",
    "                continue\n",
    "            j = min(j, f - 1)\n",
    "            while num > 0:\n",
    "                while j > 0 and num > 0:\n",
    "                    if j not in freq:\n",
    "                        freq[j] += 1\n",
    "                        num -= 1\n",
    "                        ret += f - j\n",
    "                    j -= 1\n",
    "                if j == 0 and num > 0:\n",
    "                    ret += f * num\n",
    "                    break\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        count = Counter(s)\n",
    "        distinct = set()\n",
    "        ans = 0\n",
    "        for c, cnt in count.items():\n",
    "            cnt = count[c]\n",
    "            if cnt not in distinct:\n",
    "                distinct.add(cnt)\n",
    "            else:\n",
    "                while cnt > 0 and cnt in distinct:\n",
    "                    cnt -= 1\n",
    "                    ans += 1\n",
    "                if cnt > 0:\n",
    "                    distinct.add(cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        sor = sorted(Counter(s).values(), reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(1, len(sor)):\n",
    "            if sor[i] >= sor[i - 1]:\n",
    "                target = max(0, sor[i - 1] - 1)\n",
    "                ans += sor[i] - target\n",
    "                sor[i] = target\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        lst=list(collections.Counter(s).values())\n",
    "        lst= sorted(lst , reverse=True)\n",
    "        for i in range(1,len(lst)):\n",
    "            if lst[i-1] ==0:\n",
    "                ans+=lst[i]\n",
    "                lst[i]=0\n",
    "                continue\n",
    "            if lst[i-1] == lst[i]:\n",
    "                lst[i]-=1\n",
    "                ans+=1\n",
    "            else:\n",
    "                if lst[i-1]<lst[i]:\n",
    "                    ans += lst[i]-lst[i-1]+1\n",
    "                    lst[i]=lst[i]-(lst[i]-lst[i-1]+1)\n",
    "                    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        from collections import Counter\n",
    "        count, res, used = Counter(s), 0, set()\n",
    "        for _, freq in count.items():\n",
    "            while freq > 0 and freq in used:\n",
    "                freq -= 1\n",
    "                res += 1\n",
    "            used.add(freq)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c = collections.Counter(s)\n",
    "        seen = set()\n",
    "        res = 0\n",
    "        for k, v in c.items():\n",
    "            cur = v\n",
    "            while cur>0 and cur in seen:\n",
    "                cur -= 1\n",
    "            res += v - cur\n",
    "            if cur>0:\n",
    "                seen.add(cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        res = 0\n",
    "        Set = set()\n",
    "        for i in ls:\n",
    "            while i and i in Set:\n",
    "                i -= 1\n",
    "                res += 1\n",
    "            Set.add(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        ls.sort()\n",
    "        #print(ls)\n",
    "        res = 0\n",
    "        for i in range(24, -1, -1):\n",
    "            if ls[i] and ls[i]>=ls[i+1]:\n",
    "                t = 1 if ls[i+1]>0 else 0\n",
    "                res += ls[i]-ls[i+1]+t\n",
    "                ls[i] = ls[i+1]-t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        freq = {}\n",
    "        for c in s:\n",
    "            freq[c] = freq.get(c,0) + 1\n",
    "        freq_cnt = {}\n",
    "        for cnt in freq.values():\n",
    "            freq_cnt[cnt] = freq_cnt.get(cnt,0) + 1\n",
    "        deletion = 0\n",
    "        freq_set = list(freq_cnt)\n",
    "        for freq,cnt in freq_cnt.items():\n",
    "            while cnt > 1:\n",
    "                deletion += 1\n",
    "                cnt -= 1\n",
    "                new_freq = freq - 1\n",
    "                while new_freq in freq_set and new_freq > 0:\n",
    "                    deletion += 1\n",
    "                    new_freq -= 1\n",
    "                if new_freq > 0:\n",
    "                    freq_set.append(new_freq)\n",
    "        return deletion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        res = 0\n",
    "        Set = set()\n",
    "        for i in ls:\n",
    "            while i and i in Set:\n",
    "                i -= 1\n",
    "                res += 1\n",
    "            Set.add(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        ls.sort()\n",
    "        #print(ls)\n",
    "        res = 0\n",
    "        for i in range(24, -1, -1):\n",
    "            if ls[i] and ls[i]>=ls[i+1]:\n",
    "                t = 1 if ls[i+1]>0 else 0\n",
    "                res += ls[i]-ls[i+1]+t\n",
    "                ls[i] = ls[i+1]-t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        sor = sorted(Counter(s).values(), reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(1, len(sor)):\n",
    "            if sor[i] >= sor[i - 1]:\n",
    "                target = max(0, sor[i - 1] - 1)\n",
    "                ans += sor[i] - target\n",
    "                sor[i] = target\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        sor = [*map(itemgetter(1), Counter(s).most_common())]\n",
    "        ans = 0\n",
    "        for i in range(1, len(sor)):\n",
    "            if sor[i] >= sor[i - 1]:\n",
    "                target = max(0, sor[i - 1] - 1)\n",
    "                ans += sor[i] - target\n",
    "                sor[i] = target\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        lst=sorted(list(Counter(s).values()),reverse=True)\n",
    "        ans=0\n",
    "        for i in range(1,len(lst)):\n",
    "            if lst[i]>=lst[i-1]:\n",
    "                if lst[i-1]>0:\n",
    "                    ans+=lst[i]-lst[i-1]+1\n",
    "                    lst[i]=lst[i-1]-1\n",
    "                else:\n",
    "                    ans+=lst[i]\n",
    "                    lst[i]=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        ls.sort()\n",
    "        print(ls)\n",
    "        res = 0\n",
    "        for i in range(24, -1, -1):\n",
    "            if ls[i] and ls[i]>=ls[i+1]:\n",
    "                t = 1 if ls[i+1]>0 else 0\n",
    "                res += ls[i]-ls[i+1]+t\n",
    "                ls[i] = ls[i+1]-t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        result = 0\n",
    "        fre_set = set()\n",
    "\n",
    "        for freq in cnt.values():\n",
    "            while freq>0 and freq in fre_set:\n",
    "                result+=1\n",
    "                freq-=1\n",
    "            fre_set.add(freq)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnts: List[int] = [0] * 26\n",
    "        for ch in s:\n",
    "            cnts[ord(ch) - ord('a')] += 1\n",
    "\n",
    "        # 我们只关心字符的出现次数，不关心是哪种字符，\n",
    "        # 所以直接对 cnts 按出现次数降序排序即可\n",
    "        cnts.sort(reverse=True)\n",
    "\n",
    "        # ans 维护需要删除的字符数量\n",
    "        ans: int = 0\n",
    "        # max_cnt_allowed 表示当前字符最大允许出现的次数\n",
    "        max_cnt_allowed: int = len(s)\n",
    "        # 遍历所有出现过的字符（ cnt > 0 ）的出现次数\n",
    "        for cnt in cnts:\n",
    "            if cnt == 0:\n",
    "                break\n",
    "\n",
    "            # 如果 cnt 超过了 max_cnt_allowed ，\n",
    "            # 则需要将该字符删除至出现 max_cnt_allowed 次\n",
    "            if cnt > max_cnt_allowed:\n",
    "                ans += cnt - max_cnt_allowed\n",
    "                cnt = max_cnt_allowed\n",
    "\n",
    "            # 下一个字符最大允许出现的次数 = 当前字符出现次数 - 1 ，\n",
    "            # 同时要保证一个字符最多只能被删光\n",
    "            max_cnt_allowed = max(0, cnt - 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c=collections.Counter(s)\n",
    "        seen=set()\n",
    "        res=0\n",
    "        for k , v in c.items():\n",
    "            cur=v\n",
    "            while cur>0 and cur in seen:\n",
    "                cur-=1\n",
    "            res += v-cur\n",
    "            if cur>0:\n",
    "                seen.add(cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        freq = Counter(s)\n",
    "        d = set()\n",
    "        ans = 0\n",
    "        for a, b in freq.items():\n",
    "            while b in d:\n",
    "                ans += 1\n",
    "                b -= 1\n",
    "            if b != 0: d.add(b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "      num = sorted(collections.Counter(s).values())\n",
    "      cnt = 0\n",
    "      pre = {num[0]}\n",
    "      for i in range(1, len(num)):\n",
    "        temp = num[i]\n",
    "        while temp in pre:\n",
    "          temp -= 1\n",
    "        cnt += num[i] - temp\n",
    "        if temp:  pre.add(temp)\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        vals = list(c.values())\n",
    "        vals.sort(reverse=True)\n",
    "        last = vals[0]\n",
    "        ret = 0\n",
    "        for x in vals[1:]:\n",
    "            if x >= last - 1:\n",
    "                ret += x - last + 1\n",
    "                last -= 1\n",
    "                last = max(last, 1)\n",
    "            else:\n",
    "                last = x\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        freq = [0 for _ in range(26)]\n",
    "        for i in s:\n",
    "            freq[ord(i)-ord('a')]+=1\n",
    "        res = 0\n",
    "        freq.sort(reverse = True)\n",
    "        for j in range(1,26):\n",
    "            while freq[j-1]<=freq[j] and freq[j]>0:\n",
    "                freq[j]-=1\n",
    "                res+=1\n",
    "        return res\n",
    "# 可以构建一个hashmap来储存这个结果\n",
    "#使用字典进行计数和判重\n",
    "      \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        interval = 26\n",
    "        ret_step = 0\n",
    "        record_lst = [0] * (interval * interval * 2)\n",
    "\n",
    "        import collections\n",
    "        cnter = collections.defaultdict(int)\n",
    "        for c in s:\n",
    "            cnter[c] += 1\n",
    "        all_cnts = sorted([v for _, v in cnter.items()])\n",
    "\n",
    "        base = 1\n",
    "        curr_idx = 0\n",
    "        for idx, cnt in enumerate(all_cnts):\n",
    "            bias = (cnt - base) % interval\n",
    "            mult_idx = (cnt - base) / interval\n",
    "            mult_idx = 1 if mult_idx >=1 else 0\n",
    "            curr_idx += (mult_idx * interval + bias)\n",
    "            base = cnt\n",
    "\n",
    "            mv_idx = curr_idx\n",
    "            while mv_idx >= 0:\n",
    "                if record_lst[mv_idx] == 1:\n",
    "                    mv_idx -= 1\n",
    "                    ret_step += 1\n",
    "                else:\n",
    "                    record_lst[mv_idx] = 1\n",
    "                    break\n",
    "        return ret_step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        seen = set()\n",
    "        res = 0\n",
    "        for v in c.values():\n",
    "            cur = v\n",
    "            while cur>0 and cur in seen:\n",
    "                cur -= 1\n",
    "            res += v - cur\n",
    "            if cur>0:\n",
    "                seen.add(cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']\n",
    "        countlist = []\n",
    "        lent = len(s)\n",
    "        aSet = set()\n",
    "        res = 0\n",
    "        for substring in abc:\n",
    "            countlist.append(s.count(substring))\n",
    "        for num in countlist:\n",
    "           while num in aSet:\n",
    "               num = num-1\n",
    "               res = res+1\n",
    "           else:\n",
    "               if num>0:\n",
    "                 aSet.add(num)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = sorted(list(Counter(s).values()), reverse=True)\n",
    "        ans = 0\n",
    "        pre = set()\n",
    "        for num in cnt:\n",
    "            minus = 0\n",
    "            while num > minus and num - minus in pre:\n",
    "                minus += 1\n",
    "            pre.add(num - minus)\n",
    "            ans += minus\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        res = 0\n",
    "        Set = set()\n",
    "        for i in ls:\n",
    "            while i and i in Set:\n",
    "                i -= 1\n",
    "                res += 1\n",
    "            Set.add(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        ls = [0]*26\n",
    "        for c in s:\n",
    "            ls[ord(c)-97] += 1\n",
    "        ls.sort()\n",
    "        #print(ls)\n",
    "        res = 0\n",
    "        for i in range(24, -1, -1):\n",
    "            if ls[i] and ls[i]>=ls[i+1]:\n",
    "                t = 1 if ls[i+1]>0 else 0\n",
    "                res += ls[i]-ls[i+1]+t\n",
    "                ls[i] = ls[i+1]-t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        seen = set()\n",
    "        res = 0\n",
    "        for k, v in c.items():\n",
    "            cur = v\n",
    "            while cur>0 and cur in seen:\n",
    "                cur -= 1\n",
    "            res += v - cur\n",
    "            if cur>0:\n",
    "                seen.add(cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        lst=sorted(list(Counter(s).values()),reverse=True)\n",
    "        ans=0\n",
    "        for i in range(1,len(lst)):\n",
    "            if lst[i]>=lst[i-1]:\n",
    "                if lst[i-1]>0:\n",
    "                    ans+=lst[i]-lst[i-1]+1\n",
    "                    lst[i]=lst[i-1]-1\n",
    "                else:\n",
    "                    ans+=lst[i]\n",
    "                    lst[i]=0\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c, res, has = Counter(s).values(), 0, set()\n",
    "        for i in c:\n",
    "            while i and i in has:\n",
    "                i -= 1\n",
    "                res += 1\n",
    "            has.add(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        res = 0\n",
    "        d = set()\n",
    "        for freq in Counter(s).values():\n",
    "            if freq not in d:\n",
    "                d.add(freq)\n",
    "            else:\n",
    "                cur = freq - 1\n",
    "                while cur in d and cur >= 1:\n",
    "                    cur -= 1\n",
    "                d.add(cur)\n",
    "                res += freq - cur\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        a = list(c.values())\n",
    "        a.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(1, len(a)):\n",
    "            if a[i] >= a[i-1]:\n",
    "                if a[i-1] > 0:\n",
    "                    ans += a[i] - a[i-1] + 1\n",
    "                    a[i] = a[i-1] - 1\n",
    "                else:\n",
    "                    ans += a[i]\n",
    "                    a[i] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        c, res, has = Counter(s).values(), 0, set()\n",
    "        for i in c:\n",
    "            while i and i in has:\n",
    "                i -= 1\n",
    "                res += 1\n",
    "            has.add(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        lst = sorted(cnt.values())\n",
    "        dct = set()\n",
    "        ans = 0\n",
    "        for num in lst:\n",
    "            while num and num in dct:\n",
    "                ans += 1\n",
    "                num -= 1\n",
    "            dct.add(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(Counter(s).values())\n",
    "        ans = tmp = 0\n",
    "        sorted_k = sorted(cnt.keys(), reverse=True)\n",
    "        n = len(sorted_k)\n",
    "        for i in range(n):\n",
    "            k = sorted_k[i]\n",
    "            v = cnt[k]\n",
    "            if tmp:\n",
    "                gap = sorted_k[i - 1] - sorted_k[i] - 1\n",
    "                if tmp <= gap:\n",
    "                    ans += (tmp * (tmp + 1)) // 2\n",
    "                    tmp = 0\n",
    "                    tmp += v - 1\n",
    "                else:\n",
    "                    ans += (gap + 1) * (2 * tmp - gap) // 2\n",
    "                    tmp -= gap\n",
    "                    tmp += v - 1\n",
    "            else:\n",
    "                tmp += v - 1\n",
    "        gap = sorted_k[-1] - 1\n",
    "        if tmp <= gap:\n",
    "            ans += (tmp * (tmp + 1)) // 2\n",
    "        else:\n",
    "            ans += (gap + 1) * (2 * tmp - gap) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        lst=sorted(list(Counter(s).values()),reverse=True)\n",
    "        ans=0\n",
    "        for i in range(1,len(lst)):\n",
    "            if lst[i]>=lst[i-1]:\n",
    "                if lst[i-1]>0:\n",
    "                    ans+=lst[i]-lst[i-1]+1\n",
    "                    lst[i]=lst[i-1]-1\n",
    "                else:\n",
    "                    ans+=lst[i]\n",
    "                    lst[i]=0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        alreadylist = []\n",
    "        countlist = []\n",
    "        lent = len(s)\n",
    "        for substring in s:\n",
    "            if alreadylist.count(substring)>0:\n",
    "                continue\n",
    "            countlist.append(s.count(substring))\n",
    "            alreadylist.append(substring)\n",
    "        countlist.sort()\n",
    "        totalDelete = 0\n",
    "        gradiantList = []\n",
    "        previous = 0\n",
    "        for index in range(0,len(countlist)):\n",
    "            item = countlist[index]\n",
    "            if item>previous:\n",
    "                gradiantList.append(item)\n",
    "                previous = item\n",
    "            elif item==previous:\n",
    "                gradiantLen = len(gradiantList)\n",
    "                if previous>gradiantLen:\n",
    "                    for index in range(0,gradiantLen):\n",
    "                        lastone = gradiantList[gradiantLen-1-index]\n",
    "                        if gradiantLen-2-index >= 0:\n",
    "                            lastoneBefore = gradiantList[gradiantLen-2-index]\n",
    "                            if lastone-1>=0:\n",
    "                                gradiantList[gradiantLen-1-index] = lastone-1\n",
    "                                if lastoneBefore<lastone-1:\n",
    "                                    break\n",
    "                                else:\n",
    "                                    continue\n",
    "                        else:\n",
    "                            if gradiantLen-index >= 0 and gradiantLen-index <gradiantLen:\n",
    "                              beforeOne = gradiantList[gradiantLen-index]\n",
    "                              if lastone==beforeOne:\n",
    "                                 gradiantList[gradiantLen-1-index]=lastone-1\n",
    "                            elif index == 0 and gradiantLen == 1:\n",
    "                               gradiantList[index] = lastone-1\n",
    "                    gradiantList.append(item)\n",
    "                    for item in gradiantList:\n",
    "                        if item <= 0:\n",
    "                            gradiantList.remove(item)\n",
    "                else:\n",
    "                    #丢弃item\n",
    "                    continue \n",
    "        resultTotal = 0\n",
    "        for item in gradiantList:\n",
    "             resultTotal = resultTotal + item \n",
    "        return lent - resultTotal "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        counter = Counter(s)\n",
    "        print(counter)\n",
    "        values = list(counter.values())\n",
    "        values.sort(reverse=True)\n",
    "        print(values)\n",
    "        result = 0\n",
    "        if len(values) == 0:\n",
    "            return 0\n",
    "        max_count = values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            if values[i] < max_count:\n",
    "                max_count = values[i]\n",
    "            else:\n",
    "                if max_count < 1:\n",
    "                    result += values[i]\n",
    "                else:\n",
    "                    result += values[i] - max_count + 1\n",
    "                    max_count -= 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        tmp = {}\n",
    "        for c in s:\n",
    "            if(c not in tmp):\n",
    "                tmp[c] = 1\n",
    "            else:\n",
    "                tmp[c] += 1\n",
    "        mapping = {}\n",
    "        for k, v in tmp.items():\n",
    "            if(v not in mapping):\n",
    "                mapping[v] = 1\n",
    "            else:\n",
    "                mapping[v] += 1\n",
    "        heap = []\n",
    "        for k, v in mapping.items():\n",
    "            heapq.heappush(heap, [-k,v])\n",
    "\n",
    "        result = 0\n",
    "        while(heap):\n",
    "            k, v = heapq.heappop(heap)\n",
    "            if(v == 1):\n",
    "                continue\n",
    "            else:\n",
    "                result += v - 1\n",
    "                if(heap):\n",
    "                    k1, v1 = heapq.heappop(heap)\n",
    "                    if(k+1 == k1):\n",
    "                        heapq.heappush(heap, [k1,v1+v-1])\n",
    "                    else:\n",
    "                        heapq.heappush(heap, [k1,v1])\n",
    "                        if(k+1 < 0):\n",
    "                            heapq.heappush(heap, [k+1,v-1])\n",
    "                else:\n",
    "                    if(k+1 < 0):\n",
    "                        heapq.heappush(heap, [k+1,v-1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dic = Counter(s)\n",
    "        print(dic)\n",
    "        pq = []\n",
    "        count = 0\n",
    "        set_ = set()\n",
    "        for key, value in dic.items():\n",
    "            heapq.heappush(pq, (-value, key))\n",
    "        \n",
    "        while pq:\n",
    "            value, key = heapq.heappop(pq)\n",
    "            value = -value\n",
    "            \n",
    "            while value in set_:\n",
    "                if value == 0:\n",
    "                    break\n",
    "                value -= 1\n",
    "                count += 1\n",
    "            set_.add(value)\n",
    "            print(set_)\n",
    "            \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        sor = [*map(itemgetter(1), Counter(s).most_common())]\n",
    "        ans = 0\n",
    "        for i in range(1, len(sor)):\n",
    "            if sor[i] >= sor[i - 1]:\n",
    "                target = max(0, sor[i - 1] - 1)\n",
    "                ans += sor[i] - target\n",
    "                sor[i] = target\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        #贪心+哈希表\n",
    "        cnt=list(Counter(s).values())\n",
    "        x,ans=set(),0\n",
    "        for i in cnt:\n",
    "            while i and i in x:\n",
    "                i-=1\n",
    "                ans+=1\n",
    "            x.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        # 2,2,3,4,5,5 = 1 + 5, 4 + 2\n",
    "        cnts = collections.Counter(s)\n",
    "\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        for key, val in cnts.items():\n",
    "            og = val\n",
    "            while val in seen:\n",
    "                val -= 1\n",
    "\n",
    "            if val not in seen:\n",
    "                ans += og - val\n",
    "\n",
    "                if val:\n",
    "                    seen.add(val)\n",
    "        \n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        freqs = list(cnt.values())\n",
    "        freqs.sort(key = lambda x: -x)\n",
    "        ret, minV = 0, float('inf')\n",
    "        for x in freqs:\n",
    "            minV = min(minV, x)\n",
    "            ret += minV\n",
    "            minV = max(minV-1, 0)\n",
    "        return len(s) - ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dic = {}\n",
    "        for c in s:\n",
    "            dic[c] = 1 + dic.get(c, 0)\n",
    "        arr = []\n",
    "        for v in dic.values():\n",
    "            arr.append(v)\n",
    "        hashset = set()\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for n in arr:\n",
    "            while n in hashset:\n",
    "                n-= 1\n",
    "                res += 1\n",
    "            if n != 0:\n",
    "                hashset.add(n)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        if len(s) < 2:\n",
    "            return 0\n",
    "            \n",
    "        cnt = [0] * 26\n",
    "        for c in s:\n",
    "            i = ord(c) - ord('a')\n",
    "            cnt[i] += 1\n",
    "        \n",
    "        m = 0\n",
    "        s = defaultdict(int)\n",
    "        for n in cnt:\n",
    "            if n > 0:\n",
    "                s[n] += 1\n",
    "                m = max(m, n)\n",
    "        \n",
    "        opts = 0\n",
    "        for i in range(m, 0, -1):\n",
    "            if s[i] > 1:\n",
    "                opts += s[i] - 1\n",
    "                s[i-1] += s[i] - 1\n",
    "        return opts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dict = {}\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dict:\n",
    "                dict[s[i]] = 1\n",
    "            else:\n",
    "                dict[s[i]] += 1\n",
    "\n",
    "        print(dict)\n",
    "        s = set()\n",
    "\n",
    "        for v in dict.values():\n",
    "            print('v', v)\n",
    "            if v not in s:\n",
    "                s.add(v)\n",
    "            else:\n",
    "                for num in range(v, -1, -1):\n",
    "                    if num not in s:\n",
    "                        ans += v - num\n",
    "                        if num != 0:\n",
    "                            s.add(num)\n",
    "                        break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        ans = 0\n",
    "        times = list(cnt.values())\n",
    "        times.sort(reverse=True)\n",
    "        i = 0\n",
    "        n = len(times)\n",
    "        visited = []\n",
    "        while i<n:\n",
    "            if times[i] not in visited:\n",
    "                visited.append(times[i])\n",
    "            else:\n",
    "                ans += (times[i]-visited[-1]+1)\n",
    "                if visited[-1]!=1:\n",
    "                    visited.append(visited[-1]-1)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dic=collections.defaultdict(int)\n",
    "        l = []\n",
    "        for ch in s:\n",
    "            dic[ch]+=1\n",
    "        for ch in dic:\n",
    "            l.append(dic[ch])\n",
    "        l.sort()\n",
    "        ans = 0\n",
    "        # for i in range(len(s)):\n",
    "        sparse = []\n",
    "        # print(l)\n",
    "        lst = 0   \n",
    "        for i in range(0,len(l)):\n",
    "            if l[i]==lst:\n",
    "                if sparse:\n",
    "                    ans += l[i]-sparse[-1]\n",
    "                    sparse.pop()\n",
    "                else:\n",
    "                    ans += l[i]\n",
    "            else:\n",
    "                sparse.extend(range(lst+1,l[i]))\n",
    "                # print(sparse)\n",
    "            lst = l[i]\n",
    "        if ans<0:\n",
    "            return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        # 统计小写英文字母出现的次数\n",
    "        p = [s.count(chr(97 + i)) for i in range(26)]\n",
    "        print(p)\n",
    "        # 大到小排序\n",
    "        p.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(1, 26):\n",
    "            # 上一个次数为0时，说明频次已经用完了\n",
    "            if p[i - 1] == 0:\n",
    "                # 把当前到后面的次数都应该降为0，所以都加上\n",
    "                ans += sum(p[i:])\n",
    "                break\n",
    "            # 当出现当前次数>=上一个次数时，加上之间的落差 + 1,\n",
    "            # 当前次数比上一个次数小1\n",
    "            elif p[i] >= p[i - 1]:\n",
    "                print(p[i], p[i - 1], p[i] - p[i - 1])\n",
    "                ans += p[i] - p[i - 1] + 1\n",
    "                p[i] = p[i - 1] - 1\n",
    "            print(p)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        frequencies = Counter(s) # count the frequencies of characters\n",
    "        deletions = 0 # count of deletions\n",
    "        used_frequencies = set() # the occupied frequencies\n",
    "        \n",
    "        for char, frequency in frequencies.items():\n",
    "            while frequency > 0 and frequency in used_frequencies: # We need to delete to a unused frequency\n",
    "                frequency -= 1\n",
    "                deletions += 1\n",
    "            used_frequencies.add(frequency)\n",
    "            \n",
    "        return deletions\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dic = dict()\n",
    "        for i in s:\n",
    "            if i not in dic:\n",
    "                dic[i] = 0\n",
    "            dic[i] += 1\n",
    "        arr = []\n",
    "        for i in dic:\n",
    "            arr.append(dic[i])\n",
    "        arr = sorted(arr,reverse = True)\n",
    "        arr_1 = []\n",
    "        result = 0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in arr_1:\n",
    "                arr_1.append(arr[i])\n",
    "                continue\n",
    "            while arr[i] in arr_1:\n",
    "                arr[i] = arr[i] - 1\n",
    "                result += 1\n",
    "            if arr[i] != 0:\n",
    "                arr_1.append(arr[i])\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dic = dict()\n",
    "        for i in s:\n",
    "            if i not in dic:\n",
    "                dic[i] = 0\n",
    "            dic[i] += 1\n",
    "        arr = []\n",
    "        for i in dic:\n",
    "            arr.append(dic[i])\n",
    "        arr = sorted(arr,reverse = True)\n",
    "        arr_1 = []\n",
    "        result = 0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in arr_1:\n",
    "                arr_1.append(arr[i])\n",
    "                continue\n",
    "            while arr[i] in arr_1:\n",
    "                arr[i] = arr[i] - 1\n",
    "                result += 1\n",
    "            if arr[i] != 0:\n",
    "                arr_1.append(arr[i])\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        count = dict()\n",
    "        for item in s:\n",
    "            count[item] = count.setdefault(item, 0) + 1\n",
    "\n",
    "        count = dict( sorted(count.items(), key = lambda x:x[1], reverse = True) )\n",
    "\n",
    "        keys = list(count.keys())\n",
    "\n",
    "        delete = 0\n",
    "        for i in range(1,len(keys)):\n",
    "            if count[keys[i]] == count[keys[i-1]]:\n",
    "                delete += 1\n",
    "                count[keys[i]] -=1\n",
    "                \n",
    "            elif count[keys[i]] > count[keys[i-1]]:\n",
    "                tmp = min(count[keys[i]], count[keys[i]] - count[keys[i-1]] + 1)\n",
    "\n",
    "                delete += tmp\n",
    "                count[keys[i]] -= tmp\n",
    "            else:\n",
    "                continue\n",
    "        \n",
    "        return delete\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        counts = {}\n",
    "        de = 0\n",
    "        for c in s:\n",
    "            if c not in counts:\n",
    "                counts[c] = 1\n",
    "            else:\n",
    "                counts[c] += 1\n",
    "        l = list(counts.values())\n",
    "        l.sort()\n",
    "        print(l)\n",
    "        n = len(l)\n",
    "        pre = l[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if l[i] >= pre:\n",
    "                de += l[i] - pre + 1 if pre > 0 else l[i]\n",
    "                pre -= 1\n",
    "            else:\n",
    "                pre = l[i]\n",
    "        return de"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "\n",
    "        count = collections.Counter(s).values()\n",
    "        freq_set = set()\n",
    "        ans = 0\n",
    "        for co in count:\n",
    "            while co in freq_set:\n",
    "                co -= 1\n",
    "                ans += 1\n",
    "            if co != 0:\n",
    "                freq_set.add(co)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt = Counter(Counter(s).values())\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "        for k in cnt:\n",
    "            vis.add(k)\n",
    "        for k in cnt:\n",
    "            v = cnt[k]\n",
    "            if v == 1: continue\n",
    "            while v > 1:\n",
    "                for i in range(k - 1, 0, -1):\n",
    "                    if i not in vis:\n",
    "                        vis.add(i)\n",
    "                        ans += k - i \n",
    "                        break\n",
    "                else:\n",
    "                    ans += k\n",
    "                v -= 1\n",
    "        \n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnts = Counter(s)\n",
    "        cnts = [v for k, v in cnts.items()]\n",
    "        uniq_cnts = set()\n",
    "\n",
    "        ans = 0\n",
    "        for ii in cnts:\n",
    "            if ii not in uniq_cnts:\n",
    "                uniq_cnts.add(ii)\n",
    "                continue\n",
    "            \n",
    "            while ii != 0:\n",
    "                if ii not in uniq_cnts:\n",
    "                    uniq_cnts.add(ii)\n",
    "                    break\n",
    "                \n",
    "                ii -= 1\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        fre = Counter(s)\n",
    "\n",
    "        fre_list = list(fre.values())\n",
    "        fre_list.sort()\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, len(fre_list)) :\n",
    "            cur = i\n",
    "            while cur and fre_list[cur] and fre_list[cur] == fre_list[cur-1] :\n",
    "                ans += 1\n",
    "                fre_list[cur-1] -= 1\n",
    "                cur -= 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        # 8654443\n",
    "        # 8654321\n",
    "        # didn't consider del all ch, for instance \"b: 4, c:1, e: 1, a: 1\"\n",
    "        # del all letter that would be <=0 count\n",
    "        dic = collections.Counter(s)\n",
    "        res = 0\n",
    "        last = float('inf')\n",
    "        presum = 0\n",
    "        for x in sorted(dic.values())[::-1]:\n",
    "            cur = x \n",
    "            if x >= last:\n",
    "                cur = last -1\n",
    "            if cur > 0:\n",
    "                presum += cur\n",
    "            last = cur\n",
    "        return sum(dic.values()) - presum\n",
    "\n",
    "\n",
    "           \n",
    "           \n",
    "            \n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        count = dict()\n",
    "        for item in s:\n",
    "            count[item] = count.setdefault(item, 0) + 1\n",
    "\n",
    "        count = dict( sorted(count.items(), key = lambda x:x[1], reverse = True) )\n",
    "\n",
    "        keys = list(count.keys())\n",
    "\n",
    "        delete = 0\n",
    "        for i in range(1,len(keys)):\n",
    "            # if count[keys[i]] == count[keys[i-1]]:\n",
    "            #     delete += 1\n",
    "            #     count[keys[i]] -=1\n",
    "                \n",
    "            if count[keys[i]] >= count[keys[i-1]]:\n",
    "                tmp = min(count[keys[i]], count[keys[i]] - count[keys[i-1]] + 1)\n",
    "\n",
    "                delete += tmp\n",
    "                count[keys[i]] -= tmp\n",
    "        \n",
    "        return delete\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s).values()\n",
    "        nums = sorted(list(cnt), reverse = True)\n",
    "        print(nums)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] >= nums[i - 1]:\n",
    "                if nums[i - 1] > 0:\n",
    "                    ans += nums[i] - nums[i - 1] + 1\n",
    "                    nums[i] = nums[i - 1] - 1\n",
    "                else:\n",
    "                    ans += nums[i]\n",
    "                    nums[i] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "      num = sorted(collections.Counter(s).values())\n",
    "      cnt = 0\n",
    "      pre = {num[0]}\n",
    "      for i in range(1, len(num)):\n",
    "        temp = num[i]\n",
    "        while temp in pre:\n",
    "          temp -= 1\n",
    "        cnt += num[i] - temp\n",
    "        if temp:  pre.add(temp)\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        counter = collections.Counter(s)\n",
    "        deletions = 0\n",
    "        used = set()\n",
    "        for count in counter.values():\n",
    "            if count > 0:\n",
    "                while count in used:\n",
    "                    count -= 1\n",
    "                    deletions += 1\n",
    "                if count > 0:\n",
    "                    used.add(count)\n",
    "        return deletions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s)\n",
    "        dic = defaultdict(lambda:0)\n",
    "        for i in cnt.values():\n",
    "            dic[i] += 1\n",
    "        out = 0\n",
    "        temp = list(dic.keys())\n",
    "        for k in temp:\n",
    "            if dic[k] > 1:\n",
    "                t = dic[k]-1\n",
    "                x = k\n",
    "                while t:\n",
    "                    x -= 1\n",
    "                    if not x:\n",
    "                        out += k*t\n",
    "                        break\n",
    "                    if not dic[x]:\n",
    "                        t -= 1\n",
    "                        dic[k] -= 1\n",
    "                        dic[x] += 1\n",
    "                        out += k-x\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        from collections import Counter\n",
    "        dic = Counter(s) \n",
    "        tmp = list(dic.values())\n",
    "        tmp.sort(reverse=True)\n",
    "        res = 0\n",
    "        pre = tmp[0]\n",
    "        for i in range(1, len(tmp)):\n",
    "            if pre == 0:\n",
    "                pre = 1\n",
    "            if tmp[i] >= pre:\n",
    "                res += tmp[i]-pre+1\n",
    "                pre -= 1\n",
    "            else:\n",
    "                pre = tmp[i]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        counter = Counter(s)\n",
    "        print(counter)\n",
    "        values = list(counter.values())\n",
    "        values.sort(reverse=True)\n",
    "        print(values)\n",
    "        result = 0\n",
    "        if len(values) == 0:\n",
    "            return 0\n",
    "        max_count = values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            if values[i] < max_count:\n",
    "                max_count = values[i]\n",
    "            else:\n",
    "                max_count -= 1\n",
    "                if max_count <= 0:\n",
    "                    result += values[i]\n",
    "                else:\n",
    "                    result += values[i] - max_count\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        #贪心+哈希表\n",
    "        cnt=list(Counter(s).values())\n",
    "        x,ans=set(),0\n",
    "        for i in cnt:\n",
    "            while i and i in x:\n",
    "                i-=1\n",
    "                ans+=1\n",
    "            x.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        lst=sorted(list(Counter(s).values()),reverse=True)\n",
    "        ans=0\n",
    "        for i in range(1,len(lst)):\n",
    "            if lst[i]>=lst[i-1]:\n",
    "                if lst[i-1]>0:\n",
    "                    ans+=lst[i]-lst[i-1]+1\n",
    "                    lst[i]=lst[i-1]-1\n",
    "                else:\n",
    "                    ans+=lst[i]\n",
    "                    lst[i]=0\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        cnt = Counter(s).values()\n",
    "        nums = sorted(list(cnt), reverse = True)\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] >= nums[i - 1]:\n",
    "                if nums[i - 1] > 0:\n",
    "                    ans += nums[i] - nums[i - 1] + 1\n",
    "                    nums[i] = nums[i - 1] - 1\n",
    "                else:\n",
    "                    ans += nums[i]\n",
    "                    nums[i] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        counter = Counter(s)\n",
    "        print(counter)\n",
    "        values = list(counter.values())\n",
    "        values.sort(reverse=True)\n",
    "        print(values)\n",
    "        result = 0\n",
    "        if len(values) == 0:\n",
    "            return 0\n",
    "        max_count = values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            if values[i] < max_count:\n",
    "                max_count = values[i]\n",
    "            else:\n",
    "                if max_count <= 1:\n",
    "                    result += values[i]\n",
    "                else:\n",
    "                    result += values[i] - max_count + 1\n",
    "                    max_count -= 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dic = collections.Counter(s)\n",
    "        # {\"a\": 3, \"b\": 3, \"c\": 2}\n",
    "        print(dic)\n",
    "        visit = set()\n",
    "        res = 0\n",
    "        for v in sorted(dic.values(), reverse=False):\n",
    "            while v > 0 and v in visit: # v > 0!!!!\n",
    "                res += 1\n",
    "                v -= 1\n",
    "            visit.add(v)\n",
    "        return res\n",
    "\n",
    "# {'b': 4, 'c': 1, 'e': 1, 'a': 1} should be 2 instead of 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        res = sorted([val for key, val in Counter(s).items()], reverse=True)\n",
    "        for i in range(1, len(res)):\n",
    "            if res[i] >= res[i-1]:\n",
    "                if res[i-1] == 0:\n",
    "                    ans += res[i]\n",
    "                    res[i] = 0\n",
    "                else:\n",
    "                    ans += res[i] - res[i-1] + 1\n",
    "                    res[i] = res[i-1] - 1\n",
    "        return ans\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        hashmap = collections.Counter(s)\n",
    "        q = []\n",
    "        for _, freq in hashmap.items():\n",
    "            heapq.heappush(q, -freq)\n",
    "        \n",
    "        res = 0\n",
    "        # 把第一个放进去\n",
    "        freq = heapq.heappop(q)\n",
    "\n",
    "        while q:\n",
    "            if q[0] == freq:\n",
    "                heapq.heappop(q)\n",
    "                res += 1\n",
    "                if freq < -1: heapq.heappush(q, freq+1)\n",
    "            # 没有一样的了\n",
    "            else:\n",
    "                freq = heapq.heappop(q)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        hashmap = {}\n",
    "        result = 0\n",
    "        for i in s:\n",
    "            hashmap[i] = hashmap.get(i, 0) + 1\n",
    "        print(hashmap)\n",
    "        noSameSet = set()\n",
    "        for val in hashmap.values():\n",
    "            while val in noSameSet and val > 0:\n",
    "                val -= 1\n",
    "                result += 1\n",
    "            noSameSet.add(val)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 贪心+计数排序\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        vals = sorted([0] + list(Counter(s).values()), reverse=True)\n",
    "\n",
    "        print(vals)\n",
    "\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        pre = vals[0] + 1\n",
    "        for val in vals:\n",
    "            if pre == val:\n",
    "                res += val\n",
    "                cnt += 1\n",
    "            else:\n",
    "                while res > 0 and cnt > 0 and val < pre - 1:\n",
    "                    pre -= 1\n",
    "                    res -= pre\n",
    "                    cnt -= 1\n",
    "\n",
    "                pre = val\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletions(self, s: str) -> int:\n",
    "        dict_c= dict()\n",
    "        dict_num = dict()\n",
    "        for c in s:\n",
    "            if c in dict_c.keys():\n",
    "                dict_c[c] = dict_c[c]+1\n",
    "            else:\n",
    "                dict_c[c]=1\n",
    "        for (key, value) in dict_c.items():\n",
    "            if value in dict_num.keys():\n",
    "                dict_num[value] = dict_num[value] +1\n",
    "            else:\n",
    "                dict_num[value] = 1\n",
    "        \n",
    "        sort_key = sorted(dict_num.keys(),reverse=True)\n",
    "        print('sort_key',sort_key,dict_num)\n",
    "        res = 0 \n",
    "        for i in range(len(sort_key)):\n",
    "            key = sort_key[i]\n",
    "            if i<len(sort_key)-1:\n",
    "                next_key = sort_key[i+1]\n",
    "                if dict_num[key]>key-next_key:\n",
    "                    dict_num[next_key] = dict_num[next_key] + dict_num[key]-(key-next_key)\n",
    "                    res = res+ (key-next_key)*(key-next_key-1)/2 + (key-next_key)*(dict_num[key]-(key-next_key))\n",
    "                else: \n",
    "                    res = res+ dict_num[key]*(dict_num[key]-1)/2\n",
    "            else:\n",
    "                next_key = 0 \n",
    "                if dict_num[key] <key:\n",
    "                    res =res + dict_num[key]*(dict_num[key]-1)/2\n",
    "                else:\n",
    "                    res = res+ (key-next_key)*(key-next_key-1)/2 + (key-next_key)*(dict_num[key]-(key-next_key))\n",
    "            print('res', res,'key',key)\n",
    "        return int(res)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
